package com.jat.algorithms.sort;

import java.util.Arrays;

/**
 * @author jatchen
 * @description: 快速排序
 * @date 2021/9/2810:37 PM
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] array = {3,5,1,8,7,2,4,6};
        quick(array);
        System.out.println(Arrays.toString(array));
    }

    /**
     * 思路：
     * 选择一个基数
     * 设定两个指针i和j，从头开始遍历
     * j往后移动，每移动一位比较当前数和基数的大小
     * 如果比基数小，i往前移动一步，i和j的数交换位置
     * 如果比基数大，则继续向前移动一位
     * @param array
     */
    private static void quick(int[] array){
        sort(array,0,array.length-1);
    }

    private static void sort(int[] array,int start,int end){
        int base = array[end];//基数
        int i=start-1;//i赋值为开始值加1，因为后面有个i++
        for (int j = start; j <= end-1; j++) {
            if (array[j]<base){
                i++;//i向前移动一位
                if (i!=j){//如果i和j不相等
                    swap(array,i,j);
                }
            }
        }
        swap(array,i+1,end);
        //如果标准位置的前面的数组大于两个，需要排序
        if (i+1-start>2){
            sort(array,start,i);
        }
        //如果标准位置的后面的数组大于两个，需要排序
        if (end - i+2 >2 && end > (i+2)){
            sort(array,i+2,end);
        }
    }

    private static void swap(int[] array,int i,int j){
        int exchange = array[i];
        array[i] = array[j];
        array[j] = exchange;
    }
}
